/**
 * @file
 * Red-Black tree implementation
 */

#ifndef __RB_TREE_H
#define __RB_TREE_H

#ifndef __TREE_H
# error "Please include tree.h before rb_tree.h"
#endif

enum rb_tree_color { RED, BLACK };

struct rb_tree_node {
  enum rb_tree_color color;
  struct tree_node node;
  struct list_head list;
};

struct rb_tree {
  struct rb_tree_node *rn;
  struct list_head fn;
  int  (*_comp)(struct rb_tree_node*, struct rb_tree_node*);
  void (*_free)(struct rb_tree_node*);
};

#define INIT_RB_TREE(t, c, f) do {                          \
      INIT_LIST_HEAD(&(t)->fn);                             \
      (t)->rn = NULL;                                       \
      (t)->_comp = c;                                       \
      (t)->_free = f;                                       \
  } while(0)

#define RB_TREE_INIT(t, c, f)                   \
  {NULL, LIST_HEAD_INIT(t.fn), c, f}

#define rb_tree_empty(t)                        \
  (!(t)->rn)

#define rb_tree_entry(n, type, member)          \
  get_super_struct(n, type, member)

void rb_tree_add(struct rb_tree *tree, struct rb_tree_node *node);

void rb_tree_delete(struct rb_tree *tree, struct rb_tree_node *node);

void rb_tree_clear(struct rb_tree *tree);

int  rb_tree_check(struct rb_tree *tree);

struct rb_tree_node* rb_tree_find(struct rb_tree *tree, struct rb_tree_node *node);

#endif /* __RB_TREE_H */
